package com.cdream.basic.algorithm.leetcode.dfs;

import cn.hutool.core.collection.CollUtil;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cdream
 * @date 6/21/21
 */
public class Question1239_2 {
    private int max = 0;

    public static void main(String[] args) {
        System.out.println(new Question1239_2().maxLength(CollUtil.newArrayList("eq", "ab", "efc")));
    }

    public int maxLength(List<String> arr) {
        List<Integer> narr = new ArrayList<>();
        for (String s : arr) {
            int val = 0;
            for (char c : s.toCharArray()) {
                int ch = c - 'a';
                if (((val >> ch) &1) != 0) {
                    val = -1;
                    break;
                } else {
                    // 左移后分部在不同的位上
                    val |= 1 << ch;
                }
            }
            if (val != -1) {
                narr.add(val);
            }
        }
        dfs(narr, 0, 0);
        return max;
    }

    /**
     * @param narr   元素集合
     * @param index  索引
     * @param choose 选择元素
     */
    private void dfs(List<Integer> narr, int index, int choose) {
        if (index == narr.size()) {
            max = Math.max(Integer.bitCount(choose), max);
            return;
        }
        dfs(narr, index + 1, choose);
        if ((narr.get(index) & choose) == 0) {
            dfs(narr, index + 1, narr.get(index) | choose);
        }
    }
}
